package com.heima.leetcode.practice;

/**
 * leetcode 34 在排序数组中查找元素的第一个和最后一个位置
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/6 23:19
 */
public class E34 {

    /**
     * <h3>用leftmost和rightmost</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最左位置和最右位置
     */
    public int[] searchRange1(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = searchLeftMost(nums, target);
        result[1] = searchRightMost(nums, target);
        return result;
    }

    /**
     * 找最左的位置
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最左位置
     */
    private int searchLeftMost(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length - 1; // 右边界，包含，因为要找到target时还要进一步缩小范围
        int candidate = -1; // 记录有可能的索引
        while (left <= right) {
            int median = (left + right) >>> 1;
            if (nums[median] < target) {
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                candidate = median; // 更新候选索引
                right = median - 1;
            }
        }
        return candidate;
    }

    /**
     * 找最右的位置
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最右位置
     */
    private int searchRightMost(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length - 1; // 右边界，包含，因为要找到target时还要进一步缩小范围
        int candidate = -1; // 记录有可能的索引
        while (left <= right) {
            int median = (left + right) >>> 1;
            if (nums[median] < target) {
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                candidate = median; // 更新候选索引
                left = median + 1;
            }
        }
        return candidate;
    }

    /**
     * <h3>方法二：对上述代码的优化合并</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最左位置和最右位置
     */
    public int[] searchRange2(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = binarySearch(nums, target, true);
        result[1] = binarySearch(nums, target, false);
        return result;
    }

    /**
     * 二分查找
     *
     * @param nums       数组
     * @param target     目标值
     * @param isLeftMost 是否找最左
     * @return 最左位置或最右位置
     */
    private int binarySearch(int[] nums, int target, boolean isLeftMost) {
        int left = 0, right = nums.length - 1, candidate = -1;
        while (left <= right) {
            int median = (left + right) >>> 1;
            if (nums[median] < target) {
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                candidate = median;
                if (isLeftMost) right = median - 1;
                else left = median + 1;
            }
        }
        return candidate;
    }

    /**
     * <h3>方法三：自己写的版本</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最左位置和最右位置
     */
    public int[] searchRange3(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = nums.length == 0 ? -1 : searchLeftMost1(nums, target);
        result[1] = nums.length == 0 ? -1 : searchRightMost1(nums, target);
        return result;
    }

    /**
     * 找最左的位置
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最左位置
     */
    private int searchLeftMost1(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int median = (left + right) >> 1;
            if (nums[median] < target) {
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                right = median - 1;
            }
        }
        if (left >= nums.length || nums[left] != target) return -1;
        return left;
    }

    /**
     * 找最右的位置
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最右位置
     */
    private int searchRightMost1(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int median = (left + right) >> 1;
            if (nums[median] < target) {
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                left = median + 1;
            }
        }
        if (right < 0 || nums[right] != target) return -1;
        return right;
    }
}
